/**
 * N个月饼，每个月饼有vi的饱度和wi的好度
 * 问在不超过M饱度的情况下，且好度必须是16的倍数的情况下，最多能吃多少个月饼
 * N*M == 1E5
 * 令 Dijk 是到第i个月饼、饱度为j、余数为k吃到的最多月饼
 * 对于第i个月饼，显然只有吃与不吃两种决策，所以
 * Dijk = max(1 + D[i-1][j-vi][k-wi], D[i - 1][j][k])
 * 用刷表法做。
 * 最后检查最大的D[N][x][0]即可，其中x从1到M
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using llt = long long;
using vi = vector<int>;
using vll = vector<llt>;
using pii = pair<int, int>;
using pll = pair<llt, llt>;


int N;
int M;
vi A, B;
vector<vector<vi>> D;

int chkadd(int a, int b){
    if(-1 == a or -1 == b) return -1;
    return a + b;
}

void chkmax(int & a, int b){
    if(-1 == b) return;
    if(-1 == a or a < b) a = b;
    return;
}

int proc(){
    D.assign(N + 1, vector<vi>(M + 1, vi(17, -1)));
    D[0][0][0] = 0;

    for(int i=0;i<N;++i){
        const auto & cur = D[i];
        auto & nxt = D[i + 1];
        auto ai = A[i + 1];
        auto bi = B[i + 1];

        for(int j=0;j<=M;++j){
            for(int k=0;k<16;++k){
                if(-1 != cur[j][k]){
                    chkmax(nxt[j][k], cur[j][k]);
                    if(j + ai <= M){
                        chkmax(nxt[j + ai][(k + bi) % 16], chkadd(cur[j][k], 1));
                    }                    
                }
            }
        }
    }

    int ans = 0;
    for(int i=1;i<=M;++i) chkmax(ans, D[N][i][0]);
    return ans;
}

void work(){
    cin >> N >> M;
    A.assign(N + 1, {});
    B.assign(N + 1, {});
    for(int i=1;i<=N;++i) cin >> A[i] >> B[i];
    cout << proc() << endl;
    return;
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
    int nofkase = 1;
	// cin >> nofkase;
	while(nofkase--) work();
	return 0;
}